// 《数据挖掘：概念与技术》6.1.2 计算频繁项集

#include <bits/stdc++.h>
#include "frequent_itemset.h"

using namespace std;

namespace std {
    template<>
    struct hash<vector<int>> {
        size_t operator() (const vector<int>& s) const noexcept {
            size_t HS = 0, seed = 31, Mod = 1000000007;
            for(int i = 0; i < s.size(); ++ i) {
                HS = (((long long)HS*seed)%Mod + (size_t)s[i]) % Mod;
            }
            return  HS;
        }
    };
}

// 计算所有的闭频繁项集
namespace frequent_itemset{
    int num_obj; // 数据对象的数目
    int min_sup; // 最小支持度计数
    vector<vector<int>> data; // 数据，第一维是对象的编号，保存具体的项
    vector<vector<int>> M; // 闭频繁项集
    void read() {
        cin >> num_obj;
        cin >> min_sup;
        data.resize(num_obj);
        for(int i = 0; i < num_obj; ++ i) {
            int num_items; // 当前对象的项数
            cin >> num_items;
            data[i].resize(num_items);
            for(int j = 0; j < num_items; ++ j) {
                cin >> data[i][j];
            }
            sort(data[i].begin(),data[i].end());
        }
    }

    // 暴力求解
    vector<vector<int>> foc() {
        unordered_map<vector<int>,int> freq;
        vector<int> tmp;
        for(auto &V: data) {
            for(int S = 1; S < (1<<V.size()); ++ S) {
                tmp.clear();
                for(int i = 0; i < V.size(); ++ i) if(S&(1<<i)){
                    tmp.push_back(V[i]);
                }
                ++ freq[tmp];
            }
        }
        vector<vector<int>> ans;
        for(auto &A: freq) {
            if(A.second >= min_sup) {
                ans.push_back(A.first);
            }
        }
        freq.clear();
        return ans;
    }

    // 求所有的频繁项
    vector<vector<vector<int>>> L;
    vector<unordered_set<vector<int>>> S;
    void apriori(){
        int MX = 0;
        unordered_map<vector<int>,int> mp;
        for(int i = 0; i < data.size(); ++ i) {
            for(int &v: data[i]) ++mp[{v}];
            MX = max(MX,(int)data[i].size());
        }
        L.resize(MX+1);
        S.resize(MX+1);
        auto isSubset = [&](vector<int> &c, vector<int> &t) {
            //c in t
            if(c.size() > t.size()) return false;
            sort(c.begin(), c.end());
            sort(t.begin(), t.end());
            int j = 0;
            for(int i = 0; i < t.size(); ++ i) {
                if(j < c.size() && c[j] == t[i]) ++ j;
            }
            return (j == c.size());
        };
        auto eq = [&](vector<int> &a, vector<int> &b, int n){
            for(int i = 0; i < n; ++ i) if(a[i] != b[i]) return false;
            return true;
        };
        auto aproiri_gen = [&](vector<vector<int>> &l){
            vector<vector<int>> C;
            vector<int> tmp, tt;
            sort(l.begin(),l.end());
            for(int i = 0; i < l.size(); ++ i) {
                for(int j = 0; j < l.size(); ++ j) {
                    if(l[i].back() < l[j].back() && eq(l[i],l[j],l[i].size()-1)) {
                        tmp = l[i]; tmp.push_back(l[j].back());
                        int flag = 0;
                        for(int k = 0; k < tmp.size(); ++ k) {
                            tt = tmp;
                            tt.erase(tt.begin()+k);
                            if( S[tmp.size()-1].find(tt) == S[tmp.size()-1].end() ) {
                                flag = 1;break;
                            }
                        }
                        if(!flag) C.push_back(tmp);
                    }
                }
            }
            return C;
        };
        cout << min_sup << " minsup\n";
        // 频繁1项集
        L[1].clear();
        for(auto &a: mp) {
            // cout << a.second << "\n";
            if(a.second >= min_sup) L[1].push_back(a.first), S[1].insert(a.first);
        }
        vector<vector<int>> C;
        
        for(int i = 2; i <= MX ; ++ i) {
            mp.clear();
            C = aproiri_gen(L[i-1]);
            for(auto &t: data) {
                for(auto &c: C) if(isSubset(c, t)) {
                    ++ mp[c];
                }
            }
            for(auto &a: mp) {
                if(a.second >= min_sup) L[i].push_back(a.first), S[i].insert(a.first);
            }
            if(L[i].empty()) {
                break;
            }
        }
    }


    int fpTree::createTree(vector<vector<int>> & dataset,vector<int> ct={}, int min_sup=1){
        // 第i个事务出现的次数为ct[i], 缺省为 1
        if(ct.size() == 0) ct.resize(dataset.size(),1);
        L.clear(); tr.clear(); HeadTable.clear();
        cnt = 0;
        root = ++ cnt; tr.resize(cnt+1);
        int MX = 0;
        unordered_map<int,int> mp;
        int pt = 0;
        for(auto &data: dataset) {
            for(auto &v: data) mp[v] += ct[pt], MX = max(MX, mp[v]);
            ++ pt;
        }
        for(auto &aa: mp) {
            if(aa.second >= min_sup) L.push_back({aa.second,aa.first});
        }
        sort(L.begin(),L.end(),greater<pair<int,int>>());
        for(auto &l: L) swap(l.first,l.second); // {item, count}
        auto Ins = [&](vector<int> trans, vector<pair<int,int>> &L) {
            map<int,int> inL;
            for(auto &l: L) inL[l.first]=l.second;
            for(auto it = trans.begin(); it != trans.end(); ) {
                if(inL.find((*it)) == inL.end()) it = trans.erase(it);
                else ++ it;
            }
            sort(trans.begin(), trans.end(), [&](int a, int b)->bool{return inL[a]>inL[b];});
            return trans;
        };
        auto InsTree = [&](vector<int> &P, int ct=1) {
            int now = root;
            for(int i = 0; i < P.size(); ++ i) {
                if( tr[now].nxt.find(P[i]) == tr[now].nxt.end() ) {
                    tr[now].nxt[P[i]] = ++ cnt;
                    tr.resize(cnt+1);
                    HeadTable[P[i]].push_back(cnt);
                    tr[cnt].fa = now;
                    tr[cnt].Item = P[i];
                }
                now = tr[now].nxt[P[i]];
                tr[now].count += ct;
            }
        };
        pt = 0;
        for(auto &Trans: dataset) {
            auto P = Ins(Trans, L);
            InsTree(P, ct[pt]);
            ++ pt;
        }
        // L 按频繁项出现次数倒序排序 {item, count}
        // HeadTable 每个项对应的链表
        // tr : nxt[k] 后继是项k的节点编号，count支持度计数
        // 返回节点数目，包括 root
        return cnt;
    }
    void fpTree::output() {
        createTree(data,{},min_sup);
        for(int i = 1; i <= cnt; ++ i) {
            cout << "node - " << i << ": ";
            tr[i].output();
            cout << "\n";
        }
        cout << "HeadTable:\n";
        for(int i = 0; i < L.size(); ++ i) {
            cout << "item - " << L[i].first << ":"<<L[i].second <<">> ";
            for(int &v: HeadTable[L[i].first]) {
                cout << " -> [idx=" << v<<" "; tr[v].output(); 
                cout << "]";
            }
            cout << "\n";
        }
    }

    void test_fpTree() {
        fpTree F;
        F.output();
    }
    void calCondBs(fpTree &F, int Item_d, vector<vector<int>> &condBs, vector<int> &ct) {
        list<int> &ls = (F.HeadTable[Item_d]);
        condBs.clear();
        ct.clear();
        vector<int> tmp;
        for(auto it = ls.begin(); it != ls.end(); ++ it) {
            int u = (*it), C = F.tr[u].count;
            u = F.tr[u].fa;
            tmp.clear();
            while(u != F.root) {
                // cout << u << " : " << F.tr[u].Item << "\n";
                tmp.push_back(F.tr[u].Item);
                C = min(C, F.tr[u].count);
                u = F.tr[u].fa;
            }
            reverse(tmp.begin(), tmp.end());
            if(tmp.size()>0) condBs.push_back(tmp), ct.push_back(C);
        }
        // cout << "condBs: \n";
        // for(int i = 0; i < condBs.size(); ++ i) {
        //     cout << "[";
        //     for(auto &vv: condBs[i]) cout << vv << " ";
        //     cout << "] ct = ";
        //     cout << ct[i] << "\n";
        // }
    }
    void mineTree(fpTree &F, int min_sup, vector<vector<int>> pre, vector<vector<int>> &freqItems) {
        for(int i = (int)(F.L.size())-1; i >= 0;-- i) {
            int d = F.L[i].first;
            // cout << d << " - item\n";
            auto npre = pre;
            for(auto &v: npre) v.push_back(d);
            freqItems.insert(freqItems.end(), npre.begin(),npre.end());
            
            vector<vector<int>> condBs; // 条件基
            vector<int> ct; // 对应支持度计数
            calCondBs(F, d, condBs, ct);
            fpTree F_d;
            F_d.createTree(condBs, ct, min_sup);
            if(F_d.L.size() != 0) {
                mineTree(F_d, min_sup, npre, freqItems);
            }
        }
    }
    vector<vector<int>> freqItems;
    void fp_growth(){
        fpTree F;
        F.createTree(data,{},min_sup);
        F.output();
        mineTree(F, min_sup, {{}}, freqItems);
        cout << "sz = "<< freqItems.size() << "\n";
    }
}

/*test data
9
2
3
1 2 5
2
2 4
2
2 3
3
1 2 4
2
1 3
2
2 3
2
1 3
4
1 2 3 5
3
1 2 3
*/
